#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAXSTRLEN 255 // 串的最大长度

typedef struct
{
    char ch[MAXSTRLEN + 1]; // 存储字符数组（0位置不使用）
    int length;             // 串的实际长度
} SString;

// 计算优化后的next数组（nextval）
void GetNextval(SString T, int nextval[])
{
    int i = 1, j = 0;
    nextval[1] = 0;

    while (i < T.length)
    {
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            i++;
            j++;
            // 优化部分：若当前字符与前缀字符相同，则继承nextval值
            if (T.ch[i] != T.ch[j])
            {
                nextval[i] = j;
            }
            else
            {
                nextval[i] = nextval[j];
            }
        }
        else
        {
            j = nextval[j];
        }
    }
}

// KMP算法实现
int Index_KMP(SString S, SString T)
{
    /*
    返回子串T在主串S中的位置（从1开始计数）
    若不存在则返回0
    */
    if (T.length == 0)
        return 0; // 空串是任何串的子串

    int nextval[T.length + 1]; // 创建nextval数组
    GetNextval(T, nextval);    // 计算优化后的next数组

    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.ch[i] == T.ch[j])
        {
            i++;
            j++; // 继续比较后续字符
        }
        else
        {
            j = nextval[j]; // 模式串向右移动
        }
    }

    if (j > T.length)
    {
        return i - T.length; // 匹配成功
    }
    return 0; // 匹配失败
}

// 辅助函数：创建顺序串
bool StrAssign(SString &S, const char *chars)
{
    int len = 0;
    while (chars[len] != '\0' && len < MAXSTRLEN)
    {
        len++;
    }

    if (len == 0 || len > MAXSTRLEN)
        return false;

    for (int i = 1; i <= len; i++)
    {
        S.ch[i] = chars[i - 1];
    }
    S.length = len;
    return true;
}

// 打印串
void PrintString(SString S)
{
    for (int i = 1; i <= S.length; i++)
    {
        printf("%c", S.ch[i]);
    }
    printf("\n");
}

int main()
{
    SString S, T;

    // 测试用例1：正常匹配
    StrAssign(S, "ababcabcacbab");
    StrAssign(T, "abcac");
    printf("主串: ");
    PrintString(S);
    printf("子串: ");
    PrintString(T);
    printf("KMP匹配位置: %d\n\n", Index_KMP(S, T));

    // 测试用例2：存在多个部分匹配
    StrAssign(S, "aaaaabaaaaac");
    StrAssign(T, "aaaaac");
    printf("主串: ");
    PrintString(S);
    printf("子串: ");
    PrintString(T);
    printf("KMP匹配位置: %d\n\n", Index_KMP(S, T));

    // 测试用例3：不匹配情况
    StrAssign(S, "aaabbbccc");
    StrAssign(T, "aabbd");
    printf("主串: ");
    PrintString(S);
    printf("子串: ");
    PrintString(T);
    printf("KMP匹配位置: %d\n\n", Index_KMP(S, T));

    return 0;
}